package main.leetcode.clockin.March;

/**
 * 409.最长回文串
 *
 * <p>给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
 *
 * <p>在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
 *
 * <p>注意: 假设字符串的长度不会超过 1010。
 *
 * <p>示例 1: 输入: "abccccdd" 输出: 7 解释: 我们可以构造的最长的回文串是"dccaccd", 它的长度是 7。
 */
public class day19 {
    // 关键思路：字符串长度 - （ 出现奇数次的字符个数 - 1）
    public static void main(String[] args) {
        System.out.println(new day19().longestPalindrome("aaaAaaaa"));
    }

    //    public int longestPalindrome(String s) {
    //        int n = s.length();
    //        if (n < 2) return n;
    //        int flag = 0;
    //        char[] c = s.toCharArray();
    //        Arrays.sort(c);
    //        int count = 1, res = 0;
    //        for (int i = 1; i < n; i++) {
    //            if (c[i] == c[i - 1]) ++count;
    //            else {
    //                res += (count >> 1) * 2; // 有几对
    //                if (flag == 0 && (count & 1) == 1) flag = 1; // 单个字母
    //                count = 1;
    //            }
    //        }
    //        if (count == 1 || (count & 1) == 1) flag = 1;
    //        if (count != 1) res += (count >> 1) * 2;
    //        return res + flag;
    //    }

    public int longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return n;
        int[] count = new int[52];
        for (char c : s.toCharArray()) {
            if (c < 'a') count[c - 'A']++;
            else count[c - 'a' + 26]++;
        }
        int x = 0;
        for (int i : count) {
            if ((i & 1) == 1) x++;
        }
        return x == 0 ? n : n - x + 1;
    }
}
